package leetcode_git;

/**
 * @author huangxiaoming
 * @date 2022/6/3
 **/
public class Test6 {

    /**
     * 矩阵的最小路径和
     * @param args
     */
    public static void main(String[] args) {
        int[][] numbers = new int[3][3];
        int[] col1 = new int[]{1, 3, 1};
        int[] col2 = new int[]{1, 5, 1};
        int[] col3 = new int[]{4, 2, 1};
        numbers[0] = col1;
        numbers[1] = col2;
        numbers[2] = col3;
        System.out.println(minPathSum(numbers));
    }

    public static int minPathSum(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (j == 0) {
                    dp[j] = dp[j];        // 只能从上侧走到该位置
                } else if (i == 0) {
                    dp[j] = dp[j - 1];    // 只能从左侧走到该位置
                } else {
                    dp[j] = Math.min(dp[j - 1], dp[j]);
                }
                dp[j] += grid[i][j];
            }
        }
        return dp[n - 1];
    }
}
